{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Good People Based on Statements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumGood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #基于陈述统计最多好人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>游戏中存在两种角色：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>好人</strong>：该角色只说真话。</li>\n",
    "\t<li><strong>坏人</strong>：该角色可能说真话，也可能说假话。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>statements</code> ，大小为 <code>n x n</code> ，表示 <code>n</code> 个玩家对彼此角色的陈述。具体来说，<code>statements[i][j]</code> 可以是下述值之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code> 表示 <code>i</code> 的陈述认为 <code>j</code> 是 <strong>坏人</strong> 。</li>\n",
    "\t<li><code>1</code> 表示 <code>i</code> 的陈述认为 <code>j</code> 是 <strong>好人</strong> 。</li>\n",
    "\t<li><code>2</code> 表示 <code>i</code> 没有对 <code>j</code> 作出陈述。</li>\n",
    "</ul>\n",
    "\n",
    "<p>另外，玩家不会对自己进行陈述。形式上，对所有&nbsp;<code>0 &lt;= i &lt; n</code> ，都有 <code>statements[i][i] = 2</code> 。</p>\n",
    "\n",
    "<p>根据这 <code>n</code> 个玩家的陈述，返回可以认为是 <strong>好人</strong> 的 <strong>最大</strong> 数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/01/15/logic1.jpg\" style=\"width: 600px; height: 262px;\">\n",
    "<pre><strong>输入：</strong>statements = [[2,1,2],[1,2,2],[2,0,2]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>每个人都做一条陈述。\n",
    "- 0 认为 1 是好人。\n",
    "- 1 认为 0 是好人。\n",
    "- 2 认为 1 是坏人。\n",
    "以 2 为突破点。\n",
    "- 假设 2 是一个好人：\n",
    "    - 基于 2 的陈述，1 是坏人。\n",
    "    - 那么可以确认 1 是坏人，2 是好人。\n",
    "    - 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：\n",
    "        - 说真话。在这种情况下会出现矛盾，所以假设无效。\n",
    "        - 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。\n",
    "    - <strong>在认为 2 是好人的情况下，这组玩家中只有一个好人。</strong>\n",
    "- 假设 2 是一个坏人：\n",
    "    - 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：\n",
    "        - 说真话。在这种情况下，0 和 1 都是坏人。\n",
    "            - <strong>在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。</strong>\n",
    "        - 说假话。在这种情况下，1 是好人。\n",
    "            - 由于 1 是好人，0 也是好人。\n",
    "            - <strong>在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。</strong>\n",
    "在最佳情况下，至多有两个好人，所以返回 2 。\n",
    "注意，能得到此结论的方法不止一种。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/01/15/logic2.jpg\" style=\"width: 600px; height: 262px;\">\n",
    "<pre><strong>输入：</strong>statements = [[2,0],[0,2]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>每个人都做一条陈述。\n",
    "- 0 认为 1 是坏人。\n",
    "- 1 认为 0 是坏人。\n",
    "以 0 为突破点。\n",
    "- 假设 0 是一个好人：\n",
    "    - 基于与 0 的陈述，1 是坏人并说假话。\n",
    "    - <strong>在认为 0 是好人的情况下，这组玩家中只有一个好人。</strong>\n",
    "- 假设 0 是一个坏人：\n",
    "    - 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：\n",
    "        - 说真话。在这种情况下，0 和 1 都是坏人。\n",
    "            - <strong>在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。</strong>\n",
    "        - 说假话。在这种情况下，1 是好人。\n",
    "            - <strong>在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。</strong>\n",
    "在最佳情况下，至多有一个好人，所以返回 1 。 \n",
    "注意，能得到此结论的方法不止一种。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == statements.length == statements[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>statements[i][j]</code> 的值为 <code>0</code>、<code>1</code> 或 <code>2</code></li>\n",
    "\t<li><code>statements[i][i] == 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-good-people-based-on-statements](https://leetcode.cn/problems/maximum-good-people-based-on-statements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-good-people-based-on-statements](https://leetcode.cn/problems/maximum-good-people-based-on-statements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1,2],[1,2,2],[2,0,2]]', '[[2,0],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        ans = 0\n",
    "        for mask in range(1, 1 << n):\n",
    "            def check() -> bool:\n",
    "                for i in range(n):\n",
    "                    for j in range(n):\n",
    "                        if i == j:\n",
    "                            continue\n",
    "                        if statements[i][j] == 0:\n",
    "                            if mask & (1 << i) and mask & (1 << j):\n",
    "                                return False\n",
    "                        elif statements[i][j] == 1:\n",
    "                            if mask & (1 << i) and not mask & (1 << j):\n",
    "                                return False\n",
    "                return True\n",
    "            \n",
    "            if check():\n",
    "                ans = max(ans, bin(mask).count(\"1\"))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        def check(i: int) -> int:\n",
    "            cnt = 0  # i 中好人个数\n",
    "            for j, row in enumerate(statements):  # 枚举 i 中的好人 j\n",
    "                if (i >> j) & 1:\n",
    "                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):\n",
    "                        return 0  # 好人 j 的某个陈述 st 与实际情况矛盾\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        return max(check(i) for i in range(1, 1 << len(statements)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        def check(i):\n",
    "            cnt = 0\n",
    "            for j, row in enumerate(statements):\n",
    "                if (i >> j) & 1:\n",
    "                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):\n",
    "                        return 0\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        return max(check(i) for i in range(1, 1 << len(statements)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        ans = 0\n",
    "        for i in range(1,1 << n):\n",
    "            cishu = 0\n",
    "            flag = True\n",
    "            for j, state in enumerate(statements):\n",
    "                #if i & (1 << j):\n",
    "                if (i >> j) & 1:\n",
    "                    cishu += 1\n",
    "                    for k, v in enumerate(state):\n",
    "                        #if v < 2 and i & (1 << k) != v:\n",
    "                        if v < 2 and (i >> k) & 1 != v:\n",
    "                            flag = False\n",
    "                            break\n",
    "                if not flag:\n",
    "                    break\n",
    "            if flag:\n",
    "                ans = max(ans, cishu)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        a = statements\n",
    "        n = len(a)\n",
    "        def check(st):\n",
    "            for i in range(n):\n",
    "                if st >> i & 1:\n",
    "                    for j, x in enumerate(a[i]):\n",
    "                        if x == 0 and st >> j & 1 == 1:\n",
    "                            return False\n",
    "                        if x == 1 and st >> j & 1 == 0:\n",
    "                            return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        for i in range(1 << n):\n",
    "            if check(i):\n",
    "                ans = max(ans, i.bit_count())\n",
    "        return ans\n",
    "                    \n",
    "                \n",
    "                    \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        def check(mask):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if j == i:\n",
    "                        continue\n",
    "                    if (statements[i][j] == 0 and mask >> j & 1) or (statements[i][j] == 1 and not mask >> j & 1):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for mask in range(1, 1<<n):\n",
    "            if check(mask):\n",
    "                ans = max(ans, mask.bit_count())\n",
    "        return ans\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        N = len(statements)\n",
    "        goods = [[] for _ in range(N)]\n",
    "        bads = [[] for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if statements[i][j] == 1:\n",
    "                    goods[i].append(j)\n",
    "                elif statements[i][j] == 0:\n",
    "                    bads[i].append(j)\n",
    "        ans = 0\n",
    "        for state in range((1 << N) - 1, -1, -1):\n",
    "            if state.bit_count() <= ans:\n",
    "                continue\n",
    "            success = True\n",
    "            for i in range(N):\n",
    "                if (state >> i) & 1:\n",
    "                    for j in goods[i]:\n",
    "                        if (state >> j) & 1 == 0:\n",
    "                            success = False\n",
    "                            break\n",
    "                    for j in bads[i]:\n",
    "                        if (state >> j) & 1 == 1:\n",
    "                            success = False\n",
    "                            break\n",
    "                if not success:\n",
    "                    break\n",
    "            if success and state.bit_count() > ans:\n",
    "                ans = state.bit_count()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        \n",
    "        def check(good_set):\n",
    "            for i in good_set:\n",
    "                for j in range(n):\n",
    "                    if j == i:\n",
    "                        continue\n",
    "                    if statements[i][j] == 0 and j in good_set:\n",
    "                        return False\n",
    "                    if statements[i][j] == 1 and j not in good_set:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        max_good = 0\n",
    "        for size in range(1, n + 1):\n",
    "            for good_set in combinations(range(n), size):\n",
    "                if check(good_set):\n",
    "                    max_good = max(max_good, size)\n",
    "        \n",
    "        return max_good"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n=len(statements)\n",
    "        \n",
    "        def check(mask):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i==j :\n",
    "                        continue\n",
    "                    \n",
    "                    if statements[i][j]==0 and mask&(1<<i)==(1<<i) and mask&(1<<j)==(1<<j):\n",
    "                        return False\n",
    "                    if statements[i][j]==1 and mask&(1<<i)==(1<<i)  and mask&(1<<j)!=(1<<j):\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        mx=0\n",
    "        for i in range(1,1<<n):\n",
    "            if check(i)==True:\n",
    "         \n",
    "                mx=max(mx,bin(i).count(\"1\"))\n",
    "                print(bin(i))\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        good = [0] * n\n",
    "        bad = [0] * n\n",
    "        for i, statement in enumerate(statements):\n",
    "            g = 0\n",
    "            b = (1 << n) - 1\n",
    "            for j, x in enumerate(statement):\n",
    "                if x == 1:\n",
    "                    g |= 1 << j\n",
    "                elif x == 0:\n",
    "                    b &= ~(1 << j)\n",
    "            good[i], bad[i] = g, b\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            vaild = True\n",
    "            for j in range(n):\n",
    "                if 1 << j & i:\n",
    "                    if i & good[j] != good[j] or i | bad[j] != bad[j]:\n",
    "                        vaild = False\n",
    "                        break\n",
    "            if vaild:\n",
    "                ans = max(ans, i.bit_count())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        judge_lst = [2] * n\n",
    "        num = func1(judge_lst,statements)\n",
    "        return num\n",
    "\t\n",
    "def func1(judge_lst,statements):\n",
    "    n = len(judge_lst)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "\n",
    "    if judge_lst[-1] == 1:\n",
    "        return 1 + func1(judge_lst[:-1],statements)\n",
    "    if judge_lst[-1] == 0:\n",
    "        return func1(judge_lst[:-1],statements)\n",
    "\t\n",
    "    num1 = num2 = -15\n",
    "    # 假设是好人\n",
    "    lst1 = judge_lst[:]\n",
    "    n = len(lst1) - 1\n",
    "    if check_good(lst1,statements, n):\n",
    "        num1 = 1 + func1(lst1[:-1],statements)\n",
    "\t\t\n",
    "    # 假设是坏人\n",
    "    lst2 = judge_lst[:]\n",
    "    n = len(lst2) - 1\n",
    "    if check_bad(lst2,statements, n):\n",
    "        num2 = func1(lst2[:-1],statements)\n",
    "\t\n",
    "    # 如果都矛盾\n",
    "    return max(num1,num2)\n",
    "\n",
    "def check_good(lst1, statements,n):\n",
    "    tmp = statements[n][:n]\n",
    "    # 我说别人\n",
    "    for i, v in enumerate(tmp):\n",
    "        if v == 1 and lst1[i] == 0:\n",
    "            return False\n",
    "        if v == 0 and lst1[i] == 1:\n",
    "            return False\n",
    "        if v == 1:\n",
    "            lst1[i] = 1\n",
    "            if not check_good(lst1,statements,i):\n",
    "                return False\n",
    "\n",
    "        if v == 0:\n",
    "            lst1[i] = 0\n",
    "            if not check_bad(lst1,statements,i):\n",
    "                return False\n",
    "\n",
    "    # 别人说我\n",
    "    for j in range(n):\n",
    "        if statements[j][n] == 0:\n",
    "            if lst1[j] == 1:\n",
    "                return False\n",
    "            lst1[j] = 0\n",
    "            if not check_bad(lst1,statements,j):\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def check_bad(lst2, statements,n):\n",
    "    # 别人说我\n",
    "    for j in range(n):\n",
    "        if statements[j][n] == 1:  # 我是坏人，但有人说我是好人，那么他是坏人\n",
    "            if lst2[j] == 1:\n",
    "                return False\n",
    "            lst2[j] = 0\n",
    "            if not check_bad(lst2,statements,j):\n",
    "                return False\n",
    "    return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        def check(i):\n",
    "            cnt = 0\n",
    "            for j, row in enumerate(statements):\n",
    "                if i >> j & 1:\n",
    "                    for k, st in enumerate(row):\n",
    "                        if st < 2 and st != ((i >> k) & 1): \n",
    "                            #print(i, j, k, st, bin(i)[2:])\n",
    "                            return 0\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        return max(check(i) for i in range(1, (1 << n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        有 n 个人，每个人可能是好人，也可能是坏人，\n",
    "        因此这 n 个人的好坏有 2^n 种情况。\n",
    "\n",
    "        二进制枚举好人（一共 2^n 种情况），\n",
    "        然后根据好人的陈述来判断合法性：\n",
    "\n",
    "        因为好人只说真话，那么：\n",
    "            - 好人对好人的陈述只能是 1 或 2，即不能是 0\n",
    "            - 好人对坏人的陈述只能是 0 或 2，即不能是 \n",
    "        \"\"\"\n",
    "\n",
    "        def check(good: List[int], bad: List[int]) -> bool:\n",
    "            # 1. 检查好人对好人的陈述\n",
    "            # 好人对好人的陈述只能是 1 或 2，即不能是 0\n",
    "            for i in good:\n",
    "                for j in good:\n",
    "                    if i != j and statements[i][j] == 0:\n",
    "                        return False\n",
    "            \n",
    "            # 2. 检查好人对坏人的陈述\n",
    "            # 好人对坏人的陈述只能是 0 或 2，即不能是 1\n",
    "            for i in good:\n",
    "                for j in bad:\n",
    "                    if statements[i][j] == 1:\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        n = len(statements)\n",
    "        res = 0\n",
    "        # 二进制枚举好人\n",
    "        for mask in range(1 << n):\n",
    "            # good: 好人\n",
    "            #  bad: 坏人\n",
    "            good, bad = [], []\n",
    "            \n",
    "            for i in range(n):\n",
    "                if mask & 1:\n",
    "                    good.append(i)\n",
    "                else:\n",
    "                    bad.append(i)\n",
    "                mask >>= 1\n",
    "\n",
    "            if check(good, bad):\n",
    "                res = max(res, len(good))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        def check(state):\n",
    "            g = set()\n",
    "            for i in range(n):\n",
    "                if state & 1 << i:\n",
    "                    g.add(i)\n",
    "            res = set()\n",
    "            for i in g:\n",
    "                for j in range(n):\n",
    "                    if statements[i][j] == 0 and j in g:\n",
    "                        return False\n",
    "                    elif statements[i][j] == 1 and j not in g:\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "            \n",
    "        ans = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            if check(i):\n",
    "                ans = max(ans, i.bit_count())\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        res = 0\n",
    "        def check(mask:int)->bool:\n",
    "            for i in range(n):\n",
    "                if (1 << i) & mask:\n",
    "                    for j in range(n):\n",
    "                        if statements[i][j] < 2:\n",
    "                            if (mask >> j) & 1 ^ statements[i][j]:\n",
    "                                return False\n",
    "            return True\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                res = max(res,i.bit_count())\n",
    "\n",
    "        \n",
    "    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        def check(i: int) -> int:\n",
    "            cnt = 0  # i 中好人个数\n",
    "            for j, row in enumerate(statements):  # 枚举 i 中的好人 j\n",
    "                if (i >> j) & 1:\n",
    "                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):\n",
    "                        return 0  # 好人 j 的某个陈述 st 与实际情况矛盾\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        return max(check(i) for i in range(1, 1 << len(statements)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, 1 << n):\n",
    "            score = 0\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    score += 1\n",
    "                    if all(statements[j][k] == (i >> k) & 1 for k in range(n) if statements[j][k] < 2):\n",
    "                        continue\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                ans = max(ans, score)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        def check(i: int) -> int:\n",
    "            cnt = 0  # i 中好人个数\n",
    "            for j, row in enumerate(statements):  # 枚举 i 中的好人 j\n",
    "                if (i >> j) & 1:\n",
    "                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):\n",
    "                        return 0  # 好人 j 的某个陈述 st 与实际情况矛盾\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        return max(check(i) for i in range(1, 1 << len(statements)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self): \n",
    "        self.max_total = 0\n",
    "        \n",
    "    def backtracking(self, statements, player, good, bad): \n",
    "        # base case \n",
    "        if player == len(statements): \n",
    "            self.max_total = max(len(good), self.max_total)\n",
    "            return \n",
    "        \n",
    "        # backtracking \n",
    "        for i in range(player, len(statements)): \n",
    "            # prune \n",
    "            if i in bad:    \n",
    "                continue \n",
    "                \n",
    "            new_good = [j for j in range(len(statements[i])) if statements[i][j] == 1]\n",
    "            new_good.append(i)\n",
    "            new_bad = [j for j in range(len(statements[i])) if statements[i][j] == 0]\n",
    "                        \n",
    "            new_good = [x for x in new_good if x not in good]\n",
    "            new_bad = [x for x in new_bad if x not in bad]\n",
    "            \n",
    "            if len(set(good+new_good).intersection(set(bad+new_bad))) > 0:\n",
    "                # prune \n",
    "                pass \n",
    "            else: \n",
    "                self.backtracking(statements, player+1, good+new_good, bad+new_bad)\n",
    "            if i not in bad:\n",
    "                bad.append(i)\n",
    "        \n",
    "        if len(set(good).intersection(set(bad))) > 0:\n",
    "            pass \n",
    "        else: \n",
    "            self.max_total = max(len(good), self.max_total)\n",
    "        return \n",
    "                    \n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        self.backtracking(statements, 0, [], [])\n",
    "        return self.max_total \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        ret = 0\n",
    "        for status in range(1 << n):\n",
    "            good = [0] * n\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if status & 1 << i:\n",
    "                    good[i] = 1\n",
    "                    cnt += 1\n",
    "            for i in range(n):\n",
    "                g = good[i]\n",
    "                if not g:\n",
    "                    continue\n",
    "                flag = 0\n",
    "                for j in range(n):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    g2 = good[j] == statements[i][j] or statements[i][j] == 2\n",
    "                    if not g2:\n",
    "                        flag = 1\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "            else:\n",
    "                ret = max(ret, cnt)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        N = len(statements)\n",
    "        known = [-1] * N\n",
    "        ans = 0\n",
    "\n",
    "        def traceback(p):\n",
    "            nonlocal ans, known\n",
    "            if p == N: \n",
    "                ans = max(ans, known.count(True))\n",
    "                return\n",
    "            \n",
    "            known_ = known.copy()\n",
    "\n",
    "            if known[p] is False: \n",
    "                traceback(p + 1)\n",
    "            elif known[p] is True:\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "                known = known_\n",
    "            else:\n",
    "                \n",
    "                known[p] = False\n",
    "                traceback(p + 1)\n",
    "                \n",
    "                known = known_\n",
    "                known[p] = True\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "                known = known_\n",
    "            \n",
    "\n",
    "        traceback(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        def check(f):  # 0: bad, 1: good\n",
    "            for i in range(n):\n",
    "                if f & (1 << i) == 0: continue\n",
    "                for j in range(n):\n",
    "                    if statements[i][j] == 2: continue\n",
    "                    if statements[i][j] != ((f >> j) & 1):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1 << n):\n",
    "            if check(i):\n",
    "                ans = max(ans, i.bit_count())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements) \n",
    "        ans = 0 \n",
    "        for i in range(1 << n):\n",
    "            flag = 1\n",
    "            cnt= 0 \n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    for k in range(n):\n",
    "                        if (statements[j][k] == 1 and (i >> k) & 1 == 0) or (statements[j][k] == 0 and (i>>k)&1 == 1):\n",
    "                            flag = 0\n",
    "                            break\n",
    "                    if flag == 0:\n",
    "                        break \n",
    "                    cnt += 1\n",
    "            if flag: \n",
    "                ans = max(ans, cnt) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        N = len(statements)\n",
    "        known = [-1] * N\n",
    "        ans = 0\n",
    "\n",
    "        def traceback(p):\n",
    "            nonlocal ans, known\n",
    "            if p == N: \n",
    "                ans = max(ans, known.count(True))\n",
    "                return\n",
    "            \n",
    "            known_ = known.copy()\n",
    "\n",
    "            if known[p] is False: \n",
    "                traceback(p + 1)\n",
    "            elif known[p] is True:\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "                # known = known_\n",
    "            else:\n",
    "                \n",
    "                known[p] = False\n",
    "                traceback(p + 1)\n",
    "\n",
    "                known = known_\n",
    "                known[p] = True\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "                # known = known_\n",
    "            \n",
    "\n",
    "        traceback(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\r\n",
    "        def check(i: int) -> int:\r\n",
    "            cnt = 0  # i 中好人个数\r\n",
    "            for j, row in enumerate(statements):  # 枚举 i 中的好人 j\r\n",
    "                if (i >> j) & 1:\r\n",
    "                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):\r\n",
    "                        return 0  # 好人 j 的某个陈述 st 与实际情况矛盾\r\n",
    "                    cnt += 1\r\n",
    "            return cnt\r\n",
    "\r\n",
    "        return max(check(i) for i in range(1, 1 << len(statements)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        ifgood = [2] * n # 表示n个人都不知道是好是坏\n",
    "        val = func1(statements, ifgood)\n",
    "        return max(0, val)\n",
    "        \n",
    "def sayifgood(statements, lstgood, x, flg):\n",
    "    cur = lstgood[x]\n",
    "    if cur == flg:\n",
    "        return True\n",
    "    if cur != 2:\n",
    "        return False\n",
    "    lstgood[x] = flg\n",
    "    if flg == 1: # 我是好人，我说话才有用\n",
    "        for i, how in enumerate(statements[x][:x]): # 我怎么说其他人\n",
    "            if how == 0:\n",
    "                if lstgood[i] == 0:\n",
    "                    continue\n",
    "                elif lstgood[i] == 1:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 0):\n",
    "                    return False   # 我说他是坏人，他就是坏人\n",
    "            elif how == 1:\n",
    "                if lstgood[i] == 1:\n",
    "                    continue\n",
    "                elif lstgood[i] == 0:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 1):\n",
    "                    return False   # 我说他是好人，他就是好人\n",
    "            else:\n",
    "                assert how == 2 # do nothing, 我没说他\n",
    "    # 看看别人怎么说我\n",
    "    for i in range(x):\n",
    "        how = statements[i][x]\n",
    "        if how == 2:\n",
    "            continue\n",
    "        if how != flg: # 谁说错我了，都是坏人\n",
    "            if not sayifgood(statements, lstgood, i, 0):\n",
    "                return False   # 我说他是坏人，他就是坏人\n",
    "    return True\n",
    "\n",
    "def func1(statements, ifgood):\n",
    "    n = len(ifgood)\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    howlast = ifgood[-1]\n",
    "    if howlast == 0: # 最后一人是坏人\n",
    "        return func1(statements, ifgood[:n-1])\n",
    "    if howlast == 1: # 最后一人是好人\n",
    "        return 1 + func1(statements, ifgood[:n-1])\n",
    "    assert howlast == 2 # 最后一人未确认\n",
    "\n",
    "    n3 = -15; n4 = -15\n",
    "    # 先假定他是好人\n",
    "    ifgood1 = ifgood[:]\n",
    "    if sayifgood(statements, ifgood1, n-1, 1):\n",
    "        n3 = 1 + func1(statements, ifgood1[:n-1])\n",
    "    # 再假定他是坏人\n",
    "    ifgood2 = ifgood[:]\n",
    "    if sayifgood(statements, ifgood2, n-1, 0):\n",
    "        n4 = func1(statements, ifgood2[:n-1])\n",
    "    return max(n3,n4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        # 指责对方为坏人，则不可能同时为好人\n",
    "        dislike = [set() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if statements[i][j] == 0:\n",
    "                    dislike[i].add(j)\n",
    "                    dislike[j].add(i)\n",
    "        # 对于同一个人j的判断结果不同，则不可能同时为好人\n",
    "        for j in range(n):\n",
    "            good = []\n",
    "            bad = []\n",
    "            for i in range(n):\n",
    "                if statements[i][j] == 0:\n",
    "                    bad.append(i)\n",
    "                if statements[i][j] == 1:\n",
    "                    good.append(i)\n",
    "            for x in good:\n",
    "                for y in bad:\n",
    "                    dislike[x].add(y)\n",
    "                    dislike[y].add(x)\n",
    "\n",
    "        # 认为对方是好人，则必须同时都是好人\n",
    "        like = [set() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if statements[i][j] == 1:\n",
    "                    like[i].add(j)\n",
    "\n",
    "        def check():\n",
    "            # 判断不存在不可能同时为好人的组合\n",
    "            for x in lst:\n",
    "                for y in dislike[x]:\n",
    "                    if y in lst:\n",
    "                        return False\n",
    "            # 判断必须同时为好人的组合\n",
    "            for x in lst:\n",
    "                for y in like[x]:\n",
    "                    if y not in lst:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # 使用状态压缩进行枚举\n",
    "        ans = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            lst = set([j for j in range(n) if i & (1 << j)])\n",
    "            m = len(lst)\n",
    "            if check() and m > ans:\n",
    "                ans = m\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(statements)\n",
    "        m = 2 ** n\n",
    "        good = [False] * n\n",
    "        for x in range(m):\n",
    "            count = 0\n",
    "            for i in range(n):\n",
    "                if x % 2 == 1:\n",
    "                    good[i] = True\n",
    "                    count += 1\n",
    "                else:\n",
    "                    good[i] = False\n",
    "                x //= 2\n",
    "            if count > res and self.verify(statements, good):\n",
    "                res = count\n",
    "        return res\n",
    "\n",
    "    def verify(self, statements: List[List[int]], good: List[bool]) -> bool:\n",
    "        n = len(statements)\n",
    "        for i in range(n):\n",
    "            if good[i]:\n",
    "                for j in range(n):\n",
    "                    if good[j] and statements[i][j] == 0:\n",
    "                        return False\n",
    "                    if not good[j] and statements[i][j] == 1:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        def check(combin):\n",
    "            for i in combin:\n",
    "                for j in range(n):\n",
    "                    if (statements[i][j] == 0 and j in combin) or (statements[i][j] == 1 and j not in combin):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        for l in range(n, 0, -1):\n",
    "            for combin in combinations(range(n), l):\n",
    "                if check(combin):\n",
    "                    return l\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        \n",
    "        def check(good_set):\n",
    "            for i in good_set:\n",
    "                for j in range(n):\n",
    "                    if j == i:\n",
    "                        continue\n",
    "                    if statements[i][j] == 0 and j in good_set:\n",
    "                        return False\n",
    "                    if statements[i][j] == 1 and j not in good_set:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        max_good = 0\n",
    "        for size in range(1, n + 1):\n",
    "            for good_set in combinations(range(n), size):\n",
    "                if check(good_set):\n",
    "                    max_good = max(max_good, size)\n",
    "        \n",
    "        return max_good\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.maximumGood([[1, 0], [1, 1]]))  # 应输出 1\n",
    "print(sol.maximumGood([[1, 0, 0], [2, 1, 0], [1, 1, 1]]))  # 应输出 2\n",
    "print(sol.maximumGood([[0, 0], [0, 1]]))  # 应输出 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        judge_lst = [2] * n\n",
    "        num = func1(judge_lst,statements)\n",
    "        return num\n",
    "\t\n",
    "def func1(judge_lst,statements):\n",
    "\tn = len(judge_lst)\n",
    "\tif n == 0:\n",
    "\t\treturn 0\n",
    "\t\t\n",
    "\tif judge_lst[-1] == 1:\n",
    "\t\treturn 1 + func1(judge_lst[:-1],statements)\n",
    "\tif judge_lst[-1] == 0:\n",
    "\t\treturn func1(judge_lst[:-1],statements)\n",
    "\t\n",
    "\tnum1 = num2 = -15\n",
    "\t# 假设是好人\n",
    "\tlst1 = judge_lst[:]\n",
    "\tif sayifgood(statements, lst1, n - 1, 1):\n",
    "\t\tnum1 = 1 + func1(lst1[:-1],statements)\n",
    "\t\t\n",
    "\t# 假设是坏人\n",
    "\tlst2 = judge_lst[:]\n",
    "\tif sayifgood(statements, lst2, n - 1, 0):\n",
    "\t\tnum2 = func1(lst2[:-1],statements)\n",
    "\t\n",
    "\t# 如果都矛盾\n",
    "\treturn max(num1,num2)\n",
    "\t\n",
    "def sayifgood(statements, lstgood, x, flg):\n",
    "    cur = lstgood[x]\n",
    "    if cur == flg:\n",
    "        return True\n",
    "    if cur != 2:\n",
    "        return False\n",
    "    lstgood[x] = flg\n",
    "    if flg == 1:  # 我是好人，我说话才有用\n",
    "        for i, how in enumerate(statements[x][:x]):  # 我怎么说其他人\n",
    "            if how == 0:\n",
    "                if lstgood[i] == 0:\n",
    "                    continue\n",
    "                elif lstgood[i] == 1:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 0):\n",
    "                    return False  # 我说他是坏人，他就是坏人\n",
    "            elif how == 1:\n",
    "                if lstgood[i] == 1:\n",
    "                    continue\n",
    "                elif lstgood[i] == 0:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 1):\n",
    "                    return False  # 我说他是好人，他就是好人\n",
    "            else:\n",
    "                assert how == 2  # do nothing, 我没说他\n",
    "    # 看看别人怎么说我\n",
    "    for i in range(x):\n",
    "        how = statements[i][x]\n",
    "        if how == 2:\n",
    "            continue\n",
    "        if how != flg:  # 谁说错我了，都是坏人\n",
    "            if not sayifgood(statements, lstgood, i, 0):\n",
    "                return False  # 我说他是坏人，他就是坏人\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "\n",
    "        def check(mask):\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if statements[i][j] == 2:\n",
    "                        continue\n",
    "                    if statements[i][j] ^ (mask >> j & 1):\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        for mask in range(1, 1<<n):\n",
    "            if check(mask):\n",
    "                ans = max(ans, mask.bit_count())\n",
    "        return ans\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        def check(i):\n",
    "            n = len(statements)\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for k, x in enumerate(statements[j]):\n",
    "                        if x < 2 and i >> k & 1 != x:\n",
    "                            return 0\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        return max(check(x) for x in range(1, 1 << len(statements)))                  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        res = 0\n",
    "        for mask in range(1 << n):\n",
    "            isGood = [False] * n\n",
    "            for i in range(n):\n",
    "                isGood[i] = mask & 1 == 1\n",
    "                mask >>= 1\n",
    "            flag = True\n",
    "            for i in range(n):\n",
    "                if isGood[i]:\n",
    "                    for j in range(n):\n",
    "                        if (statements[i][j] == 0 and isGood[j]) or (statements[i][j] == 1 and not isGood[j]):\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if not flag:\n",
    "                        break\n",
    "            if flag:\n",
    "                res = max(res, sum(isGood))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        \n",
    "        def check():\n",
    "            for x in good:\n",
    "                for y in range(n):\n",
    "                    w = statements[x][y]\n",
    "                    if w == 2:\n",
    "                        continue\n",
    "                    if w == 1 and y not in good:\n",
    "                        return False\n",
    "                    if w == 0 and y not in bad:\n",
    "                        return False\n",
    "            return True\n",
    "                    \n",
    "        n = len(statements)\n",
    "        ans = 0\n",
    "        for i in range(1, 1<<n):\n",
    "            good = set([j for j in range(n) if i & (1<<j)])\n",
    "            bad = set([j for j in range(n) if not i & (1<<j)])\n",
    "            if check() and len(good) > ans:\n",
    "                ans = len(good)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        \n",
    "        def check(good_set):\n",
    "            for i in good_set:\n",
    "                for j in range(n):\n",
    "                    if j == i:\n",
    "                        continue\n",
    "                    if statements[i][j] == 0 and j in good_set:\n",
    "                        return False\n",
    "                    if statements[i][j] == 1 and j not in good_set:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        max_good = 0\n",
    "        for size in range(1, n + 1):\n",
    "            for good_set in combinations(range(n), size):\n",
    "                if check(good_set):\n",
    "                    max_good = max(max_good, size)\n",
    "        \n",
    "        return max_good\n",
    "\n",
    "# 测试\n",
    "sol = Solution()\n",
    "print(sol.maximumGood([[1, 0], [1, 1]]))  # 应输出 1\n",
    "print(sol.maximumGood([[1, 0, 0], [2, 1, 0], [1, 1, 1]]))  # 应输出 2\n",
    "print(sol.maximumGood([[0, 0], [0, 1]]))  # 应输出 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        judge_lst = [2] * n\n",
    "        num = func1(judge_lst,statements)\n",
    "        return num\n",
    "\t\n",
    "def func1(judge_lst,statements):\n",
    "\tn = len(judge_lst)\n",
    "\tif n == 0:\n",
    "\t\treturn 0\n",
    "\t\t\n",
    "\tif judge_lst[-1] == 1:\n",
    "\t\treturn 1 + func1(judge_lst[:-1],statements)\n",
    "\tif judge_lst[-1] == 0:\n",
    "\t\treturn func1(judge_lst[:-1],statements)\n",
    "\t\n",
    "\tnum1 = num2 = -15\n",
    "\t# 假设是好人\n",
    "\tlst1 = judge_lst[:]\n",
    "\tif sayifgood(statements, lst1, n - 1, 1):\n",
    "\t\tnum1 = 1 + func1(lst1[:-1],statements)\n",
    "\t\t\n",
    "\t# 假设是坏人\n",
    "\tlst2 = judge_lst[:]\n",
    "\tif sayifgood(statements, lst2, n - 1, 0):\n",
    "\t\tnum2 = func1(lst2[:-1],statements)\n",
    "\t\n",
    "\t# 如果都矛盾\n",
    "\treturn max(num1,num2)\n",
    "\t\n",
    "def sayifgood(statements, lstgood, x, flg):\n",
    "    cur = lstgood[x]\n",
    "    if cur == flg:\n",
    "        return True\n",
    "    if cur != 2:\n",
    "        return False\n",
    "    lstgood[x] = flg\n",
    "    if flg == 1:  # 我是好人，我说话才有用\n",
    "        for i, how in enumerate(statements[x][:x]):  # 我怎么说其他人\n",
    "            if how == 0:\n",
    "                if lstgood[i] == 0:\n",
    "                    continue\n",
    "                elif lstgood[i] == 1:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 0):\n",
    "                    return False  # 我说他是坏人，他就是坏人\n",
    "            elif how == 1:\n",
    "                if lstgood[i] == 1:\n",
    "                    continue\n",
    "                elif lstgood[i] == 0:\n",
    "                    return False\n",
    "                if not sayifgood(statements, lstgood, i, 1):\n",
    "                    return False  # 我说他是好人，他就是好人\n",
    "            else:\n",
    "                assert how == 2  # do nothing, 我没说他\n",
    "    # 看看别人怎么说我\n",
    "    for i in range(x):\n",
    "        how = statements[i][x]\n",
    "        if how == 2:\n",
    "            continue\n",
    "        if how != flg:  # 谁说错我了，都是坏人\n",
    "            if not sayifgood(statements, lstgood, i, 0):\n",
    "                return False  # 我说他是坏人，他就是坏人\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        n = len(statements)\n",
    "        res = 0\n",
    "        def check(mask:int)->bool:\n",
    "            for i in range(n):\n",
    "                # i是好人，他的话有用\n",
    "                if (1 << i) & mask:\n",
    "                    for j in range(n):\n",
    "                        # i有判断j是好人还是好人\n",
    "                        if statements[i][j] < 2:\n",
    "                            # i的判断结果有误，则mask这种情况不正确\n",
    "                            if (mask >> j) & 1 ^ statements[i][j]:\n",
    "                                return False\n",
    "            return True\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                res = max(res,i.bit_count())\n",
    "    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGood(self, statements: List[List[int]]) -> int:\n",
    "        N = len(statements)\n",
    "        known = [-1] * N\n",
    "        ans = 0\n",
    "\n",
    "        def traceback(p):\n",
    "            nonlocal ans, known\n",
    "            if p == N: \n",
    "                ans = max(ans, known.count(True))\n",
    "                return\n",
    "\n",
    "            if known[p] is False: \n",
    "                traceback(p + 1)\n",
    "            elif known[p] is True:\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "            else:\n",
    "                known_ = known.copy()\n",
    "                known[p] = False\n",
    "                traceback(p + 1)\n",
    "\n",
    "                known = known_\n",
    "                known[p] = True\n",
    "                for idx, s in enumerate(statements[p]):\n",
    "                    if s == 0:\n",
    "                        if known[idx] is True: return\n",
    "                        else: known[idx] = False\n",
    "                    elif s == 1:\n",
    "                        if known[idx] is False: return\n",
    "                        else: known[idx] = True\n",
    "            \n",
    "                traceback(p + 1)\n",
    "            \n",
    "\n",
    "        traceback(0)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
